package com.LeeCode;

import java.util.PriorityQueue;

/**
 * 找出第 K 大的异或坐标值
 */

public class Code1738 {
    public static void main(String[] args) {
        int[][] matrix = {
                {5, 2},
                {1, 6}
        };
        int k = 4;
        System.out.println(new Code1738().kthLargestValue(matrix, k));
    }

    public int kthLargestValue(int[][] matrix, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int m = matrix.length, n = matrix[0].length;
        int[][] preXor = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int num = matrix[i][j] ^ preXor[i][j + 1] ^ preXor[i + 1][j] ^ preXor[i][j];
                preXor[i + 1][j + 1] = num;
                if (pq.size() < k) {
                    pq.offer(num);
                } else {
                    if (num > pq.peek()) {
                        pq.poll();
                        pq.offer(num);
                    }
                }
            }
        }
        return pq.peek();
    }
}
